// https://www.lintcode.com/problem/single-number-iii/

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer array
     */
    public List<Integer> singleNumberIII(int[] A) {
        // write your code here
        List<Integer> ret = new ArrayList<>();
        Arrays.sort(A);
        int i = 0;
        while ((i + 1) < A.length) {
            if ((A[i] ^ A[i + 1]) != 0) {
                break;
            }
            i += 2;
        }
        ret.add(A[i]);
        ret.add(_singleNumber(A, i + 1, A.length));
        return ret;
    }
    
    protected int _singleNumber(int[] A, int start, int end) {
        int ret = 0;
        while (start < end) {
            ret ^= A[start];
            ++start;
        }
        return ret;
    }
}